package com.leetcode.Redraiment的走法;

import java.util.Scanner;

/**
 * <p>
 * 参考：https://www.nowcoder.com/practice/24e6243b9f0446b081b1d6d32f2aa3aa?tpId=37&tqId=21326&rp=1&ru=%2Fta%2Fhuawei%2F&qru=%2Fta%2Fhuawei%2Fquestion-ranking&tab=answerKey
 * 动态规划问题
 * </p>
 *
 * @author: Sunny
 * @date: 2021/3/11
 * @version: v1.0.0
 */
public class Main {

    public static void main(String[] args) {
        Main main = new Main();
        main.walk();
    }

    public void walk() {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            /**
             * 控制台通过键盘输入：
             * 6
             * 2 5 1 5 4 5
             */
            int n = scanner.nextInt();
            int[] array = new int[n];
            for (int i = 0; i < n; i++) {
                array[i] = scanner.nextInt(); // netInt：以"空格or换行符"做为分割符，作为程序的输入，能通过"scanner.nextInt()"获取到。
            }
            System.out.println(getMaxSteps(array, n));
        }

    }

    public static int getMaxSteps(int[] arr, int n) {
        // 存放当前位置的最长字串长度
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1; // 初始定义1步
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        // 找到dp数组中的最大值即可
        int max = 0;
        for (int i = 0; i < dp.length; i++)
            if (dp[i] > max) {
                max = dp[i];
            }
        return max;
    }

}
